package teaching;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: fzykd
 * Date: 2022-11-08
 * Time: 11:19
 */

//希尔排序
public class ShellSort {
    public static void main(String[] args) {
        int[] arr1 = {101,34,119,1};
        int[] arr = new int[80000];
        //产生随机数
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int) (Math.random()*800000); //生成[0-800000)数
        }
        Date data1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date1 = simpleDateFormat.format(data1);
        System.out.println("排序前的时间输出=" + date1);

        //运行插入排序
        shellSort(arr);

        Date data2 = new Date();
        String date2 = simpleDateFormat.format(data2);
        System.out.println("排序后的时间输出=" + date2);

    }

    //移位发
    public static void shellSort(int[] arr){
        //先分组 然后逐步减小
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            //从第gap个元素开始 逐个对其所在的元素直接插入排序
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                int tmp = arr[i];
                if (arr[j] < arr[j - gap]){
                    while (j-gap >= 0 && tmp < arr[j-gap]){
                        //移动
                        arr[j] = arr[j-gap];
                        j -= gap;
                    }
                    //退出 找到了位置
                    arr[j] = tmp;
                }
            }
        }
    }



    //循环
    public static void shellSort2(int[] arr){
        int tmp = 0;
        int count = 0;
        for (int gap = arr.length/2; gap > 0 ; gap/=2) {
            for (int i = gap; i < arr.length; i++) {
                //遍历各组中所有数据的元素
                for (int j = i-gap; j >= 0 ; j -= gap) {
                    //如果当前的元素大于步长后的元素 那么就交换
                    if (arr[j] > arr[j+gap]){
                        tmp = arr[j];
                        arr[j] = arr[j+gap];
                        arr[j+gap] = tmp;
                    }
                }
            }
            //System.out.println("希尔排序第"+(++count)+"轮:" + Arrays.toString(arr));
        }
    }

    //逐步推到 交换法
    public static void shellSort1(int[] arr){
        //第一轮
        //10个数据分成10/2=5组
        int tmp = 0;
        for (int i = 5; i < arr.length; i++) {
            //遍历各组中所有数据的元素
            for (int j = i-5; j >= 0 ; j -= 5) {
                //如果当前的元素大于步长后的元素 那么就交换
                if (arr[j] > arr[j+5]){
                    tmp = arr[j];
                    arr[j] = arr[j+5];
                    arr[j+5] = tmp;
                }
            }
        }
        System.out.println("第一轮:" + Arrays.toString(arr));

        //第二轮
        //10个数据分成10/2/2 = 2组
         tmp = 0;
        for (int i = 2; i < arr.length; i++) {
            //遍历各组中所有数据的元素
            for (int j = i-2; j >= 0 ; j -= 2) {
                //如果当前的元素大于步长后的元素 那么就交换
                if (arr[j] > arr[j+2]){
                    tmp = arr[j];
                    arr[j] = arr[j+2];
                    arr[j+2] = tmp;
                }
            }
        }
        System.out.println("第二轮:" + Arrays.toString(arr));

        //10个数据分成10/2/2/2 = 1组
        tmp = 0;
        for (int i = 1; i < arr.length; i++) {
            //遍历各组中所有数据的元素
            for (int j = i-1; j >= 0 ; j -= 1) {
                //如果当前的元素大于步长后的元素 那么就交换
                if (arr[j] > arr[j+1]){
                    tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
            }
        }
        System.out.println("第三轮:" + Arrays.toString(arr));
    }




}
